// #include <iostream>
// #include <cstring>
// using namespace std;

// const int N = 1001;
// int n, V, v[N], w[N];
// int dp[N][N];

// int main()
// {
//     cin >> n >> V;
//     for (int i = 1; i <= n; ++i)
//     {
//         cin >> v[i] >> w[i];
//     }
//     // 问题1
//     for(int i=1;i<=n;++i)// 物品编号
//     {
//         for(int j=1;j<=V;++j) // 背包容量
//         {
//             dp[i][j] = dp[i-1][j];// i位置物品不选，该情况一定存在
//             if(j-v[i] >= 0)//判断一下取前面哪一个位置的值，使得背包容量足够我们这里选取i位置物品
//                 dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]] + w[i]); //加上i位置物品的价值
//         }
//     }
//     cout << dp[n][V] << endl;
//     // dp表清空内部数据
//     memset(dp,0,sizeof(dp));
//     // 问题2
//     // -1表示i位置一个物品就直接大于背包最大容量了
//     for(int j=1;j<=V;++j)
//     {
//         dp[0][j] = -1; // 物品为0没有，想使得背包容量为j这种情况是不存在的，-1
//     }
//     for(int i=1;i<=n;++i)// 物品编号
//     {
//         for(int j=1;j<=V;++j) // 背包容量
//         {
//             dp[i-1][j]就不用判断了，因为你前i-1如果为-1，我不选i位置
//             那么[i][j]结果就是[i-1][j]，你[i-1][j]为-1，前面都选不出来，那么我这里也就选不出来，那么直接等于前面的-1也是正常的
//             dp[i][j] = dp[i-1][j];// i位置物品不选，该情况一定存在
//             判断如果我选i位置物品，但是i-1前面位置物品的体积为-1，不是j-v[i]，那么就不能恰好装满
//             也就是说，必须在前i-1个物品中，凑出j-v[i]的体积，不然选了i位置物品，怎么也不能刚刚好装满背包，要么体积大了，要么体积小了
//             if(j-v[i] >= 0 && dp[i-1][j-v[i]]!= -1)
//                 dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]] + w[i]); //加上i位置物品的价值
//         }
//     }
//     cout << (dp[n][V] == -1 ?0:dp[n][V]) << endl; //最后为-1表示所有物品的体积都大于背包容量，返回0
//     return 0;
// }

// ///--- 优化 ---滚动数组
// #include <iostream>
// #include <cstring>
// using namespace std;

// const int N = 1001;
// int n, V, v[N], w[N];
// int dp[N]; // 只需要一维数组

// int main()
// {
//     cin >> n >> V;
//     for (int i = 1; i <= n; ++i)
//     {
//         cin >> v[i] >> w[i];
//     }
//     for(int i=1;i<=n;++i)
//     {
//         因为用的是一个数组来进行滚动，我j位置的值，等于我之前j位置的值，和我j-v[i]位置的值，那么如果从左往右更新，j-v[i]位置的值提前被修改了
//         for(int j=V;j>=1;--j) // 修改遍历顺序，从右往左
//         {
//             // 干掉横坐标，相当于dp[j] = dp[j]没有了
//             // dp[i][j] = dp[i-1][j];
//             if(j-v[i] >= 0)
//                 dp[j] = max(dp[j],dp[j-v[i]] + w[i]);
//         }
//     }
//     cout << dp[V] << endl;
//     memset(dp,0,sizeof(dp));
//     // 依旧是干掉横坐标
//     for(int j=1;j<=V;++j)
//     {
//         dp[j] = -1;  // 这里一维数组1到v初始化为-1，下面可以正常进行循环处理，因为dp[0]位置的初始是0 --->>>memset(dp,0,sizeof(dp));
//     }
//     for(int i=1;i<=n;++i)
//     {
//         for(int j=V;j>=1;--j)
//         {
//             // dp[i][j] = dp[i-1][j];
//             if(j-v[i] >= 0 && dp[j-v[i]]!= -1)
//                 dp[j] = max(dp[j],dp[j-v[i]] + w[i]);
//         }
//     }
//     cout << (dp[V] == -1 ?0:dp[V]) << endl;
//     return 0;
// }

///--- 优化 --- 基于滚动数组，对循环判断条件优化，提高一定的时间效率
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1001;
int n, V, v[N], w[N];
int dp[N]; // 只需要一维数组

int main()
{
    cin >> n >> V;
    for (int i = 1; i <= n; ++i)
    {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; ++i)
    {
        // 因为用的是一个数组来进行滚动，我j位置的值，等于我之前j位置的值，和我j-v[i]位置的值，那么如果从左往右更新，j-v[i]位置的值提前被修改了
        for (int j = V; j >= v[i]; --j) // 修改遍历顺序，从右往左
        {
            // 干掉横坐标，相当于dp[j] = dp[j]没有了
            // dp[i][j] = dp[i-1][j];
            // 这里将v[i]放到循环判断里面，因为j是从大到小，那么如果我j-v[i]小于0，那么我j--之后j-v[i]还是小于0，所以j要>=v[i]，保证空间足够
            // if(j- v[i]>= 0)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[V] << endl;
    memset(dp, 0, sizeof(dp));

    for (int j = 1; j <= V; ++j)
    {
        dp[j] = -1; // 依旧是干掉横坐标
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = V; j >= v[i]; --j)
        {
            // 同理，进行修改
            // dp[i][j] = dp[i-1][j];
            // if(j-v[i] >= 0 && dp[j-v[i]]!= -1)
            // j要>=v[i]，保证背包容量足够
            if (dp[j - v[i]] != -1) // 这个判断还是要进行的，判断我前面位置的容量是不是有效的，有效+j位置的容量就刚刚好
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    // 第V列dp【V】就是容量为满的最大价值
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
    return 0;
}

// class Solution {
// public:
//     bool canPartition(vector<int>& nums) {
//         int sum = 0;
//         for(auto e : nums)
//             sum += e;
//         if(sum % 2 == 1)
//             return false;
//         int n = nums.size();
//         int num = sum/2;
//         // 这里开sum/2 + 1列
//         vector<vector<bool>> dp(n+1,vector<bool>(sum+1));
//         // dp[i][j] : 数组0到i位置的所有子序列，能不能加起来等于j
//         for(int i=0;i<=n;++i)
//             dp[i][0] = true;
//         for(int i=1;i<=n;++i)
//         {
//             for(int j=1;j<=num;++j)
//             {
//                 // 不选i位置能不能前面0到i-1位置的数能不能加为j
//                 dp[i][j] = dp[i-1][j];
//                 // 如果我选了i位置数据，但是i位置数据一个数就大于我们要求的j了，那么就不能选了
//                 // 如果我选了i位置数据，我不选i和选了i有一个成立，那么[i][j]就为真
//                 if(j >= nums[i-1])
//                     // 如果前面存在j-nums[i-1]，那么[i][j] 有一个为真就为真
//                     dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
//             }
//         }
//         // 打印0到n的数据，能不能相加为num。如果0到n可以和为num，那么剩下的数据和一定也等于num，因为num是sum/2得到
//         return dp[n][num];
//     }
// };

// 优化---滚动数组
class Solution
{
public:
    bool canPartition(vector<int> &nums)
    {
        int sum = 0;
        for (auto e : nums)
            sum += e;
        if (sum % 2 == 1)
            return false;
        int n = nums.size();
        int num = sum / 2;
        // 这里开sum/2 + 1列
        vector<bool> dp(sum + 1);
        // dp[i][j] : 数组0到i位置的所有子序列，能不能加起来等于j
        dp[0] = true;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = num; j >= nums[i - 1]; --j)
            {
                // 去掉横坐标
                // dp[i][j] = dp[i-1][j];
                dp[j] = dp[j] || dp[j - nums[i - 1]];
                // if(j >= nums[i-1])
                // dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
            }
        }
        return dp[num];
    }
};
// class Solution {
// public:
//     int findTargetSumWays(vector<int>& nums, int target) {
//         // dp[i][j] : nums从0到i中，选取任意数和等于j，一共有多少种方法
//         // nums中分正数和负数，a是全部正数和，b是全部负数绝对值的和
//         // 那么，【a+b = sum】【a-b = target】 --->>> 【2a = target + sum】
//         int m = nums.size();
//         int sum = 0;
//         // num是所有正数和
//         for(auto e : nums)
//             sum+=e;
//         int num = (target + sum) /2;
//         // num<0表示target是一个负数，且sum里面和也小于这个负数绝对值
//         if(num < 0 || (target + sum) %2) return 0;// target + sum 一定要是一个奇数，num也一定要是一个正数
//         vector<vector<int>> dp(m+1,vector<int>(num+1));
//         dp[0][0] = 1;
//         // 如果没有数据个数i为0，那么j>0的地方全部为0，0个数和怎么可能也不能为1,2,3...所以方法为0
//         // 如果和为0，但是i有数据，其实是不能直接初始化为0的，因为如果数据个数有i个，其中包含了0数据，那么是有方法和等于j也就是0的
//         // 但是我们不需要初始化[i][0]，因为dp[i-1][j-nums[i]]中j是>=nums[i]的，当nums[i]等于0时，j=0，那么就是dp[i-1][0]
//         // 所以，我dp[i][0],只会用到dp[i-1][0],也就是正上面的值，而用不到上一行左边的值，所以不会越界！
//         for(int i=1;i<=m;++i)
//         {
//             // j因为没有初始化，所以j=0的位置是要经过下面运算的
//             for(int j=0;j<=num;++j)
//             {
//                 dp[i][j] = dp[i-1][j];
//                 if(j >= nums[i-1])
//                     // dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];
//                     dp[i][j] += dp[i-1][j-nums[i-1]]; //后面不需要加1或者加nums[i]
//             }
//         }
//         return dp[m][num];
//     }
// };

// 优化 滚动数组 --- 干掉行数，保留一行
class Solution
{
public:
    int findTargetSumWays(vector<int> &nums, int target)
    {
        // dp[i][j] : nums从0到i中，选取任意数和等于j，一共有多少种方法
        // nums中分正数和负数，num是全部正数和，b是全部负数绝对值的和
        // 那么，【num+b = sum】【num-b = target】 --->>> 【2num = target + sum】
        int m = nums.size();
        int sum = 0;
        // num是所有正数和
        for (auto e : nums)
            sum += e;
        int num = (target + sum) / 2;
        // num<0表示target是一个负数，且sum里面和也小于这个负数绝对值
        if (num < 0 || (target + sum) % 2)
            return 0; // target + sum 一定要是一个奇数，num也一定要是一个正数
        vector<int> dp(num + 1);
        dp[0] = 1;
        // 如果没有数据个数i为0，那么j>0的地方全部为0，0个数和怎么可能也不能为1,2,3...所以方法为0
        // 如果和为0，但是i有数据，其实是不能直接初始化为0的，因为如果数据个数有i个，其中包含了0数据，那么是有方法和等于j也就是0的
        // 但是我们不需要初始化[i][0]，因为dp[i-1][j-nums[i]]中j是>=nums[i]的，当nums[i]等于0时，j=0，那么就是dp[i-1][0]
        // 所以，我dp[i][0],只会用到dp[i-1][0],也就是正上面的值，而用不到上一行左边的值，所以不会越界！
        for (int i = 1; i <= m; ++i)
        {
            // j因为没有初始化，所以j=0的位置是要经过下面运算的
            for (int j = num; j >= nums[i - 1]; --j)
            {
                // dp[i][j] = dp[i-1][j];
                // if(j >= nums[i-1])
                // dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];
                // dp[i][j] += dp[i-1][j-nums[i-1]]; //后面不需要加1或者加nums[i]
                dp[j] += dp[j - nums[i - 1]];
            }
        }
        return dp[num];
    }
};
// class Solution {
// public:
//     int lastStoneWeightII(vector<int>& stones) {
//         int sum = 0;
//         for(auto e : stones)
//             sum+=e;
//         int num = sum/2;
//         int m = stones.size();
//         vector<vector<int>> dp(m+1,vector<int>(num+1));
//         for(int i=1;i<=m;++i)
//         {
//             for(int j=0;j<=num;++j)
//             {
//                 dp[i][j] = dp[i-1][j];
//                 if(j>=stones[i-1])
//                     dp[i][j] = max(dp[i-1][j],dp[i-1][j-stones[i-1]] + stones[i-1]);
//             }
//         }
//         // dp[m][num]是最接近sum/2的值，那么a = dp[m][num]，b = sum - dp[m][num]
//         // 所以最小值 = sum -dp[m][num] -dp[m][num]
//         return sum - 2 * dp[m][num];
//     }
// };

/// 优化，滚动数组
class Solution
{
public:
    int lastStoneWeightII(vector<int> &stones)
    {
        int sum = 0;
        for (auto e : stones)
            sum += e;
        int num = sum / 2;
        int m = stones.size();
        vector<int> dp(num + 1);
        for (int i = 1; i <= m; ++i)
        {
            // for(int j=0;j<=num;++j)
            for (int j = num; j >= stones[i - 1]; --j)
            {
                // dp[i][j] = dp[i-1][j];
                // if(j>=stones[i-1])
                //     dp[i][j] = max(dp[i-1][j],dp[i-1][j-stones[i-1]] + stones[i-1]);
                dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
            }
        }
        // dp[m][num]是最接近sum/2的值，那么a = dp[m][num]，b = sum - dp[m][num]
        // 所以最小值 = sum -dp[m][num] -dp[m][num]
        return sum - 2 * dp[num];
    }
};
// #include <iostream>
// #include <vector>
// #include <cstring>
// using namespace std;

// const static int N = 1001;
// int n ,V,v[N],w[N];
// int dp[N][N];
// int main()
// {
//     cin >> n >> V;
//     for(size_t i=0;i<n;++i)
//     {
//         cin >> v[i] >> w[i];
//     }
//     for(int i=1;i<=n;++i)
//     {
//         // j为0我们要使用到，但是上面没有初始化，所以这里j要从0开始
//         for(int j=0;j<=V;++j)
//         {
//             dp[i][j] = dp[i-1][j];
//             if(j-v[i-1] >= 0)
//                 dp[i][j] = max(dp[i-1][j] , dp[i][j-v[i-1]] + w[i-1]);
//         }
//     }
//     cout << dp[n][V] << endl;
//     memset(dp,0,sizeof(dp));
//     for(int j=1;j<=V;++j)
//     {
//         dp[0][j] = -1;
//     }
//     for(int i=1;i<=n;++i)
//     {
//         for(int j=0;j<=V;++j)
//         {
//             dp[i][j] = dp[i-1][j];
//             if(j-v[i-1] >= 0 && dp[i][j-v[i-1]] != -1)
//                 dp[i][j] = max(dp[i-1][j] , dp[i][j-v[i-1]] + w[i-1]);
//         }
//     }
//     cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
//     return 0;
// }

// 优化，滚动数组
////// ------ 01背包使用更新之前的值【从右往左】  完全背包使用更新之后的值【从左往右】------//////
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const static int N = 1001;
int n, V, v[N], w[N];
int dp[N];
int main()
{
    cin >> n >> V;
    for (size_t i = 0; i < n; ++i)
    {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; ++i)
    {
        // j为0我们要使用到，但是上面没有初始化，所以这里j要从0开始
        ////// ------我们这里j要从左向右更新！因为我们j位置的值是从上一行和本行的左边获取得到的
        for (int j = v[i - 1]; j <= V; ++j)
        {
            dp[j] = max(dp[j], dp[j - v[i - 1]] + w[i - 1]);
        }
    }
    cout << dp[V] << endl;
    memset(dp, 0, sizeof(dp));
    for (int j = 1; j <= V; ++j)
    {
        dp[j] = -1;
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = v[i - 1]; j <= V; ++j)
        {
            if (dp[j - v[i - 1]] != -1)
                dp[j] = max(dp[j], dp[j - v[i - 1]] + w[i - 1]);
        }
    }
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
    return 0;
}

memset(dp, 0, sizeof(dp));
for (int j = 1; j <= V; ++j)
{
    // 进一步优化，我们下面可以不使用if(dp[j-v[i-1]] != -1)判断该空间是否合理，因为求的是max值，所以只要dp[j-v[i-1]] + w[i-1]
    // 是一个最小值，那么就不会被选到 --- >>> 【确保max(dp[j] , dp[j-v[i-1]] + w[i-1])不会选到dp[j-v[i-1]] + w[i-1]】
    // dp[j] = -1;
    dp[j] = -0x3f3f3f3f; // INT_MIN的一半，防止下面进行减法，比如-w[i-1]，这样的话就减为一个正无穷大的数据了
}
for (int i = 1; i <= n; ++i)
{
    for (int j = v[i - 1]; j <= V; ++j)
    {
        // if(dp[j-v[i-1]] != -1)
        dp[j] = max(dp[j], dp[j - v[i - 1]] + w[i - 1]);
    }
}
// cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
cout << (dp[V] < 0 ? 0 : dp[V]) << endl; // 这里也修改一下，因为dp[V]不是存-1了，而是一个特别小的数
